package slidingWindow;

public class MinSubArrayLen {

    /**
     * LeetCode T209 长度最小的子数组
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     *
     * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
        int i = minSubArrayLen(3, nums);
        System.out.println(i);
    }

    //方法一：使用前缀和 + 滑动窗口
    public static int minSubArrayLen(int target, int[] nums){
        int len = nums.length;
        //右边界坐标
        int rk = 0;
        //记录左右边界的和
        int l_sum = 0, r_sum = 0;
        int ans = Integer.MAX_VALUE;
        //初始化左右边界的和
        r_sum = nums[rk];
        for (int i = 0; i < len; i++){
            //有边界向右滑动，滑动到临界值
            while (rk + 1 < len && r_sum - l_sum < target){
                rk++;
                r_sum += nums[rk];
            }
            if (r_sum - l_sum >= target){
                ans = Math.min(rk - i + 1, ans);
            }
            //左边界滑动
            l_sum += nums[i];
        }

        return ans == Integer.MAX_VALUE?0:ans;

    }

    public int minSubArrayLen01(int target, int[] nums) {
        int len = nums.length;
        //右边界
        int right = -1;
        //记录结果
        int ans = Integer.MAX_VALUE;
        //记录窗口的内容
        int sum = 0;
        //遍历数组
        for (int i = 0; i < len; i++){
            //右边界移动，使其结果能够符合边界条件
            while (right+1 < len && sum < target){
                right++;
                sum += nums[right];
            }
            //必须是符合条件时才能够收集结果，当右边界移动到最右时不一定（一定要判断临界条件）
            if (sum >= target){
                ans = Math.min(ans, right - i + 1);
            }
            //左边界向右移动
            sum -= nums[i];
        }
        return ans == Integer.MAX_VALUE?0:ans;
    }


}
